iT邦幫忙

0

[用 Python 解 LeetCode] (004) 277. Find the Celebrity

  • 分享至 

  • xImage
  •  

這題因為 leetcode鎖起來,所以我們跑去做Lintcode上面的第 645題 Find the Celebrity

題幹懶人包

從派對裡面找名人,要是名人的條件有二

  1. 大家都認識他
  2. 他不認識任何人

可以利用它提供的 API 獲取A是否認識B,比方說這樣調用Celebrity.knows(a, b),返回值是True 代表認識,False代表不認識。

一個派對最多只有一個名人,如果有名人回傳他的下標值,沒有的話回傳 -1。目標是調用最少次題目提供的 API

解法

首先假設第一個人是名人(用head 表示現在誰有可能是名人),開始循環剩下人,思維有以下兩個

  1. 如果 head 知道下一個人是誰,就代表 head 一定不是名人,所以現在第 i 個人有可能是
  2. 如果head 不知道下一個人是誰,下一個人就一定不是名人,head 保持不變

如此循環完成後,可以得到 head 現在是最有可能是名人的人,然後他不認識大家沒有用,還必須要大家都認識他,因此循環一次,一但有人不認識他,代表所有人裡面沒有人還有可能是名人。

最後因為一直以來 head 都是不知道 head 以後的人是誰,所以 head 還有可能知道他前面的人是誰。因此還需要跑一次迴圈確定前面的人他都不認識。

class Solution:
    # @param {int} n a party with n people
    # @return {int} the celebrity's label or -1
    
    def findCelebrity(self, n):
        # 首先假設第一個人是名人(用head 表示現在誰有可能是名人)
        head = 0
        for i in range(1, n):
            # 如果head 不知道下一個人是誰,下一個人就一定不是名人,head 保持不變
            if not Celebrity.knows(head, i):
                continue
            # 如果 head 知道下一個人是誰,就代表 head 一定不是名人,所以現在第 i 個人有可能是
            else:
                head = i
        # 還必須要大家都認識他,因此循環一次
        for i in range(n):
            if not Celebrity.knows(i, head):
                head = -1
                break
        # head 還有可能知道他前面的人是誰。因此還需要跑一次迴圈        
        for i in range(0, head):
            if Celebrity.knows(head, i):
                head = -1
                break
        return head

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言